package listbyorder.access001_100.test4;

/**
 * @author code_yc
 * @version 1.0
 * @date 2020/6/6 14:13
 */
public class Solution3 {

    // 解法三： 使用二分查找算法，将两个数组分成长度相等的两个数组，大数组和小数组，然后返回中间值
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        return getAns(nums1, nums2);
    }

    private double getAns(int[] A, int[] B){
        int m = A.length;
        int n = B.length;
        if (m > n) {
            // 保证A数据的长度比B数组小
            return getAns(B, A);
        }
        int iMin = 0;  // i分割位置的当前最小值
        int iMax = m;  // i分割位置的当前最大值
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = (m + n + 1) / 2 - i;  // 公式
            if (j != 0 && i != m && B[j - 1] > A[i]) {
                iMin = i + 1;   // iMin增大
            } else if (i != 0 && j != n && A[i - 1] > B[j]) {
                iMax = i - 1;   // iMax减小
            } else {   // 达到要求开始进行遍历
                int maxLeft = 0;
                if (i == 0) {
                    maxLeft = B[j - 1];
                } else if (j == 0) {
                    maxLeft = A[i - 1];
                } else {
                    maxLeft = Math.max(A[i - 1], B[j - 1]);
                }
                if ((m + n) % 2 == 1) return maxLeft;

                int minRight = 0;
                if (i == m) {
                    minRight = B[j];
                } else if (j == n) {
                    minRight = A[i];
                } else {
                    minRight = Math.min(A[i], B[j]);
                }
                return (minRight + maxLeft) / 2.0;
            }
        }
        return 0.0;
    }
}
